/*
 * @lc app=leetcode.cn id=316 lang=javascript
 *
 * [316] 去除重复字母
 */

// @lc code=start
/**
 * @param {string} s
 * @return {string}
 */
var removeDuplicateLetters = function (s) {
  const lastIndex = {};
  const has = {};
  for (let i = 0; i < s.length; i++) {
    lastIndex[s[i]] = i;
  }
  const stack = [];
  for (let i = 0; i < s.length; i++) {
    if (has[s[i]]) {
      continue;
    }
    while (stack.length && stack[stack.length - 1] > s[i] && lastIndex[stack[stack.length - 1]] > i) {
      has[stack[stack.length - 1]] = false;
      stack.pop();
    }
    has[s[i]] = true;
    stack.push(s[i]);
  }
  return stack.join('');
};
// @lc code=end